#include <stdio.h>
#include <stdlib.h>

typedef struct node {
	int data;
	struct node *next;
}NODE;

// 链表逆置
NODE *Reverse(NODE *L)
{
    NODE *pre = NULL;    // 前驱结点
    NODE *cur = L; // 当前结点
    NODE *next;          // 后继结点
    while (cur != NULL)
    {
        next = cur->next; // next记录当前结点的后继 防止断链
        cur->next = pre;  // 当前结点反向
        pre = cur;        // 下一次循环
        cur = next;
    }
    return pre;
}

// 带头结点 重排列a1ana2an-1...
// 空间复杂度O(1)
void Rearragement (NODE *L) {
	// 先将后半部分逆置 
	// 再从中间和开头同时遍历 进行重排
	NODE *slow = L, *fast = L;
	// 先找到链表中点
	// fast两步 slow一步 fast到头时 slow就在中点
	while(fast) {
		slow = slow->next;
		fast= fast->next->next;
	}
	// 从中点开始逆置
	NODE *mid = Reverse(slow);
	// 一个从尾部 一个从开始进行重排
	NODE *ptr = L->next;
	while (mid) {
		NODE *t = ptr->next;
		ptr->next = mid;
		ptr->next->next = t;
		ptr = t->next;
		mid = mid->next;
	}
}

// 测试用
NODE *NewNode(int e) {
	NODE *r = (NODE*)malloc(sizeof(NODE));
	r->data = e;
	r->next = NULL;
	return r;
}

void Append(NODE *L, int e) {
	NODE *ptr = L;
	while(ptr->next)
		ptr = ptr->next;
	ptr->next = NewNode(e);
}

void PrintList(NODE *L) {
	NODE *ptr = L->next;
	printf("head->");
	while(ptr) {
		printf("%d->", ptr->data);
		ptr = ptr->next;
	}
	printf("NULL\n");
}

int main() {
	NODE *L = NewNode(0); // 头结点
	Append(L,1);
	Append(L,2);
	Append(L,3);		
	Append(L,4);
	Append(L,5);
	Append(L,6);	
	PrintList(L);
	Rearragement(L);
	PrintList(L);
	return 0;
}
